package com.cat.graphTheory;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-minimum-time-to-reach-last-room-i/description/https://leetcode.cn/problems/find-minimum-time-to-reach-last-room-i/description/
 * @create 2025/9/23 21:09
 * @since JDK17
 */

public class Solution26 {
    public int minTimeToReach(int[][] moveTime) {
        int n = moveTime.length, m = moveTime[0].length;
        int[] d = new int[]{-1, 0, 1, 0, -1};
        int[][] dis = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dis[i], Integer.MAX_VALUE);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        pq.offer(new int[]{0, 0, 0});
        dis[0][0] = 0;
        while (!pq.isEmpty()) {
            var p = pq.poll();
            int cost = dis[p[0]][p[1]];
            if (p[2] > cost) {   // 之前出去过
                continue;
            }
            for (int i = 0; i < 4; i++) {
                int nx = p[0] + d[i], ny = p[1] + d[i + 1];
                if (nx == -1 || ny == -1 || nx == n || ny == m) {
                    continue;
                }
                int e = Math.max(cost, moveTime[nx][ny]) + 1;
                if (e < dis[nx][ny]) {
                    dis[nx][ny] = e;
                    pq.offer(new int[]{nx, ny, e});
                }
            }
        }

        return dis[n - 1][m - 1];
    }
}
